home *** CD-ROM | disk | FTP | other *** search
/ Programming Languages Suite / ProgramD2.iso / Borland / Borland C++ V5.02 / INC.PAK / LIST.H < prev    next >
C/C++ Source or Header  |  1997-05-06  |  24KB  |  840 lines
  1. #ifndef __STD_LIST__
  2. #define __STD_LIST__
  3. /* $Revision:   8.1  $ */
  4.  
  5. /***************************************************************************
  6.  *
  7.  * list - list declarations for the Standard Library
  8.  *
  9.  * $Id: list,v 1.47 1995/09/18 23:31:35 lijewski Exp $
  10.  *
  11.  ***************************************************************************
  12.  *
  13.  * Copyright (c) 1994
  14.  * Hewlett-Packard Company
  15.  *
  16.  * Permission to use, copy, modify, distribute and sell this software
  17.  * and its documentation for any purpose is hereby granted without fee,
  18.  * provided that the above copyright notice appear in all copies and
  19.  * that both that copyright notice and this permission notice appear
  20.  * in supporting documentation.  Hewlett-Packard Company makes no
  21.  * representations about the suitability of this software for any
  22.  * purpose.  It is provided "as is" without express or implied warranty.
  23.  *
  24.  *
  25.  ***************************************************************************
  26.  *
  27.  * (c) Copyright 1994, 1995 Rogue Wave Software, Inc.
  28.  * ALL RIGHTS RESERVED
  29.  *
  30.  * The software and information contained herein are proprietary to, and
  31.  * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
  32.  * intends to preserve as trade secrets such software and information.
  33.  * This software is furnished pursuant to a written license agreement and
  34.  * may be used, copied, transmitted, and stored only in accordance with
  35.  * the terms of such license and with the inclusion of the above copyright
  36.  * notice.  This software and information or any other copies thereof may
  37.  * not be provided or otherwise made available to any other person.
  38.  *
  39.  * Notwithstanding any other lease or license that may pertain to, or
  40.  * accompany the delivery of, this computer software and information, the
  41.  * rights of the Government regarding its use, reproduction and disclosure
  42.  * are as set forth in Section 52.227-19 of the FARS Computer
  43.  * Software-Restricted Rights clause.
  44.  *
  45.  * Use, duplication, or disclosure by the Government is subject to
  46.  * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
  47.  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  48.  * Contractor/Manufacturer is Rogue Wave Software, Inc.,
  49.  * P.O. Box 2328, Corvallis, Oregon 97339.
  50.  *
  51.  * This computer software and information is distributed with "restricted
  52.  * rights."  Use, duplication or disclosure is subject to restrictions as
  53.  * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
  54.  * Computer Software-Restricted Rights (April 1985)."  If the Clause at
  55.  * 18-52.227-74 "Rights in Data General" is specified in the contract,
  56.  * then the "Alternate III" clause applies.
  57.  *
  58.  **************************************************************************/
  59.  
  60. #include <stdcomp.h>
  61.  
  62. #include <function>
  63. #include <algorith>
  64. #include <iterator>
  65.  
  66. #ifndef Allocator
  67. #define Allocator allocator
  68. #include <memory>
  69. #endif
  70.  
  71. #ifndef list
  72. #define list list
  73. #endif
  74.  
  75. #ifndef RWSTD_NO_NAMESPACE
  76. namespace std {
  77. #endif
  78.  
  79. template <class T>
  80. class list
  81. {
  82.   protected:
  83.  
  84.     typedef Allocator<void>::pointer void_pointer;
  85.  
  86.     struct list_node;
  87.     friend struct list_node;
  88.  
  89.     struct list_node
  90.     {
  91.         void_pointer next;
  92.         void_pointer prev;
  93.         T            data;
  94.     };
  95.  
  96.     Allocator<list_node>  list_node_allocator;
  97.     Allocator<T>          value_allocator;
  98.  
  99.   public:
  100.     //
  101.     // types
  102.     //
  103.     typedef T                                     value_type;
  104.     typedef Allocator<T>                          value_allocator_type;
  105.     typedef Allocator<T>::pointer                 pointer;
  106.     typedef Allocator<T>::reference               reference;
  107.     typedef Allocator<T>::const_reference         const_reference;
  108.     typedef Allocator<list_node>              list_node_allocator_type;
  109.     typedef Allocator<list_node>::pointer         link_type;
  110.     typedef Allocator<list_node>::size_type       size_type;
  111.     typedef Allocator<list_node>::difference_type difference_type;
  112.  
  113.   protected:
  114.  
  115.     static size_type buffer_size ()
  116.     {
  117.         //
  118.         // Each time we allocate memory we reserve space for
  119.         // this many nodes.  This is currently tuned to
  120.         // allocate memory in 1K chunks, except for large objects.
  121.         //
  122.         return sizeof(list_node) >= 1024 ? 1 : 1024 / sizeof(list_node);
  123.     };
  124.  
  125.     struct list_node_buffer;
  126.     friend struct list_node_buffer;
  127.  
  128.     struct list_node_buffer
  129.     {
  130.         void_pointer next_buffer;
  131.         link_type    buffer;
  132.     };
  133.  
  134.   public:
  135.  
  136.     typedef Allocator<list_node_buffer>          buffer_allocator_type;
  137.     typedef Allocator<list_node_buffer>::pointer buffer_pointer;
  138.  
  139.   protected:
  140.  
  141.     Allocator<list_node_buffer>   buffer_allocator;
  142.     buffer_pointer                buffer_list;
  143.     link_type                     free_list;
  144.     link_type                     next_avail;
  145.     link_type                     last;
  146.  
  147.     void add_new_buffer ()
  148.     {
  149.         buffer_pointer tmp = buffer_allocator.allocate((size_type)1);
  150.         tmp->buffer = list_node_allocator.allocate(buffer_size());
  151.         tmp->next_buffer = buffer_list;
  152.         buffer_list = tmp;
  153.         next_avail = buffer_list->buffer;
  154.         last = next_avail + buffer_size();
  155.     }
  156.     void deallocate_buffers ();
  157.     link_type get_node ()
  158.     {
  159.         link_type tmp = free_list;
  160.         return free_list ? (free_list = (link_type)(free_list->next), tmp)
  161.             : (next_avail == last ? (add_new_buffer(), next_avail++)
  162.                : next_avail++);
  163.     }
  164.     void put_node (link_type p) { p->next = free_list; free_list = p; }
  165.  
  166.   protected:
  167.  
  168.     link_type node;
  169.     size_type length;
  170.  
  171.   public:
  172.  
  173.     class iterator;
  174.     class const_iterator;
  175.  
  176.     class iterator : public bidirectional_iterator<T, difference_type>
  177.     {
  178.         friend class list<T>;
  179.         friend class const_iterator;
  180.  
  181.       protected:
  182.  
  183.         link_type node;
  184.         iterator (link_type x) : node(x) {}
  185.  
  186.       public:
  187.  
  188.         iterator () {}
  189.         bool operator== (const iterator& x) const { return node == x.node; }
  190.         reference operator* () const { return (*node).data; }
  191.         iterator& operator++ ()
  192.         {
  193.             node = (link_type)((*node).next); return *this;
  194.         }
  195.         iterator operator++ (int)
  196.         {
  197.             iterator tmp = *this; ++*this; return tmp;
  198.         }
  199.         iterator& operator-- ()
  200.         {
  201.             node = (link_type)((*node).prev); return *this;
  202.         }
  203.         iterator operator-- (int)
  204.         {
  205.             iterator tmp = *this; --*this; return tmp;
  206.         }
  207.     };  // End of definition of iterator class.
  208.  
  209.     class const_iterator : public bidirectional_iterator<T, difference_type>
  210.     {
  211.         friend class list<T>;
  212.  
  213.       protected:
  214.  
  215.         link_type node;
  216.         const_iterator (link_type x) : node(x) {}
  217.  
  218.       public:
  219.  
  220.         const_iterator () {}
  221.         const_iterator (const iterator& x) : node(x.node) {}
  222.         bool operator== (const const_iterator& x) const {return node==x.node;}
  223.         const_reference operator* () const { return (*node).data; }
  224.         const_iterator& operator++ ()
  225.         {
  226.             node = (link_type)((*node).next); return *this;
  227.         }
  228.         const_iterator operator++ (int)
  229.         {
  230.             const_iterator tmp = *this; ++*this; return tmp;
  231.         }
  232.         const_iterator& operator-- ()
  233.         {
  234.             node = (link_type)((*node).prev); return *this;
  235.         }
  236.         const_iterator operator-- (int)
  237.         {
  238.             const_iterator tmp = *this;
  239.             --*this;
  240.             return tmp;
  241.         }
  242.     };  // End of definition of cosnt_iterator class.
  243.  
  244.     typedef reverse_bidirectional_iterator<const_iterator, value_type,
  245.                                            const_reference, difference_type>
  246.             const_reverse_iterator;
  247.     typedef reverse_bidirectional_iterator<iterator, value_type, reference,
  248.                                            difference_type>
  249.             reverse_iterator;
  250.  
  251.     //
  252.     // construct/copy/destroy
  253.     //
  254.     list () : length(0)
  255.     {
  256.         buffer_list = 0;
  257.         free_list = next_avail = last = 0;
  258.         node = get_node();
  259.         (*node).next = node;
  260.         (*node).prev = node;
  261.     }
  262.     //
  263.     // Build a list of size n with each element set to default for type T.
  264.     // This requires that T have a default constructor.
  265.     //
  266.     explicit list (size_type n) : length(0)
  267.     {
  268.         T value;
  269.         buffer_list = 0;
  270.         free_list   = next_avail = last = 0;
  271.         node        = get_node();
  272.         (*node).next = node;
  273.         (*node).prev = node;
  274.         insert(begin(), n, value);
  275.     }
  276.     //
  277.     // Build a vector of size n with each element set to a copy of value.
  278.     //
  279.     explicit list (size_type n, const T& value) : length(0)
  280.     {
  281.         buffer_list = 0;
  282.         free_list   = next_avail = last = 0;
  283.         node        = get_node();
  284.         (*node).next = node;
  285.         (*node).prev = node;
  286.         insert(begin(), n, value);
  287.     }
  288.  
  289. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  290.     template<class InputIterator>
  291.     list (InputIterator first, InputIterator locallast) : length(0)
  292.     {
  293.         buffer_list = 0;
  294.         free_list = next_avail = last = 0;
  295.         node = get_node();
  296.         (*node).next = node;
  297.         (*node).prev = node;
  298.         insert(begin(), first, locallast);
  299.     }
  300. #else
  301.     list (const_iterator first, const_iterator locallast) : length(0)
  302.     {
  303.         buffer_list = 0;
  304.         free_list = next_avail = last = 0;
  305.         node = get_node();
  306.         (*node).next = node;
  307.         (*node).prev = node;
  308.         insert(begin(), first, locallast);
  309.     }
  310.     list (const T* first, const T* locallast) : length(0)
  311.     {
  312.         buffer_list = 0;
  313.         free_list = next_avail = last = 0;
  314.         node = get_node();
  315.         (*node).next = node;
  316.         (*node).prev = node;
  317.         insert(begin(), first, locallast);
  318.     }
  319. #endif
  320.  
  321.     list (const list<T>& x) : length(0)
  322.     {
  323.         buffer_list = 0;
  324.         free_list = next_avail = last = 0;
  325.         node = get_node();
  326.         (*node).next = node;
  327.         (*node).prev = node;
  328.         insert(begin(), x.begin(), x.end());
  329.     }
  330.     ~list ()
  331.     {
  332.         erase(begin(), end());
  333.         put_node(node);
  334.         deallocate_buffers();
  335.     }
  336.     list<T>& operator= (const list<T>& x);
  337.  
  338. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  339.     template<class InputIterator>
  340.     void assign (InputIterator first, InputIterator last)
  341.     {
  342.         erase(begin(), end()); insert(begin(), first, last);
  343.     }
  344. #else
  345.     void assign (const_iterator first, const_iterator last)
  346.     {
  347.         erase(begin(), end()); insert(begin(), first, last);
  348.     }
  349.     void assign (const T* first, const T* last)
  350.     {
  351.         erase(begin(), end()); insert(begin(), first, last);
  352.     }
  353. #endif
  354.     //
  355.     // Assign n copies of default value of type T to vector.
  356.     // This requires that T have a default constructor.
  357.     //
  358. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  359.     template<class Size, class T>
  360.     void assign (Size n)
  361. #else
  362.     void assign (size_type n)
  363. #endif
  364.     {
  365.         erase(begin(), end()); insert(begin(), n, T());
  366.     }
  367.     //
  368.     // Assign n copies of t to this vector.
  369.     //
  370. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  371.     template<class Size, class T>
  372.     void assign (Size n, const T& t)
  373. #else
  374.     void assign (size_type n, const T& t)
  375. #endif
  376.     {
  377.         erase(begin(), end()); insert(begin(), n, t);
  378.     }
  379.     //
  380.     // Iterators.
  381.     //
  382.     iterator       begin ()       { return (link_type)((*node).next); }
  383.     const_iterator begin () const { return (link_type)((*node).next); }
  384.     iterator       end ()         { return node;                      }
  385.     const_iterator end ()   const { return node;                      }
  386.     reverse_iterator rbegin ()
  387.     {
  388.         reverse_iterator tmp(end()); return tmp;
  389.     }
  390.     const_reverse_iterator rbegin () const
  391.     {
  392.         const_reverse_iterator tmp(end()); return tmp;
  393.     }
  394.     reverse_iterator rend ()
  395.     {
  396.         reverse_iterator tmp(begin()); return tmp;
  397.     }
  398.     const_reverse_iterator rend () const
  399.     {
  400.         const_reverse_iterator tmp(begin()); return tmp;
  401.     }
  402.     //
  403.     // Capacity.
  404.     //
  405.     bool empty ()         const { return length == 0;                    }
  406.     size_type size ()     const { return length;                         }
  407.     size_type max_size () const { return list_node_allocator.max_size(); }
  408.     void resize (size_type new_size);
  409.     void resize (size_type new_size, T value);
  410.     //
  411.     // Element access.
  412.     //
  413.     reference       front ()       { return *begin();   }
  414.     const_reference front () const { return *begin();   }
  415.     reference       back  ()       { return *(--end()); }
  416.     const_reference back  () const { return *(--end()); }
  417.     //
  418.     // Modifiers.
  419.     //
  420.     //
  421.     // Insert default value of type T at position.
  422.     // Requires that T have a default constructor.
  423.     //
  424.     iterator insert (iterator position)
  425.     {
  426.         T x;
  427.         link_type tmp = get_node();
  428.         construct(value_allocator.address((*tmp).data), x);
  429.         (*tmp).next = position.node;
  430.         (*tmp).prev = (*position.node).prev;
  431.         (*(link_type((*position.node).prev))).next = tmp;
  432.         (*position.node).prev = tmp;
  433.         ++length;
  434.         return tmp;
  435.     }
  436.     //
  437.     // Insert x at position.
  438.     //
  439.     iterator insert (iterator position, const T& x)
  440.     {
  441.         link_type tmp = get_node();
  442.         construct(value_allocator.address((*tmp).data), x);
  443.         (*tmp).next = position.node;
  444.         (*tmp).prev = (*position.node).prev;
  445.         (*(link_type((*position.node).prev))).next = tmp;
  446.         (*position.node).prev = tmp;
  447.         ++length;
  448.         return tmp;
  449.     }
  450.     void insert (iterator position, size_type n, const T& x);
  451.  
  452. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  453.     template<class InputIterator>
  454.     void insert (iterator position, InputIterator first, InputIterator last);
  455. #else
  456.     void insert (iterator position, const T* first, const T* last);
  457.     void insert (iterator position, const_iterator first, const_iterator last);
  458. #endif
  459.  
  460.     void erase (iterator position)
  461.     {
  462.         (*(link_type((*position.node).prev))).next = (*position.node).next;
  463.         (*(link_type((*position.node).next))).prev = (*position.node).prev;
  464.         destroy(value_allocator.address((*position.node).data));
  465.         put_node(position.node);
  466.         --length;
  467.     }
  468.     void erase      (iterator first, iterator last);
  469.     void push_front (const T& x) { insert(begin(), x); }
  470.     void push_back  (const T& x) { insert(end(), x);   }
  471.     void pop_front  ()           { erase(begin());     }
  472.     void pop_back   ()           { iterator tmp = end(); erase(--tmp); }
  473.     void swap (list<T>& x)
  474.     {
  475. #ifndef RWSTD_NO_NAMESPACE
  476.         std::swap(node, x.node);
  477.         std::swap(length, x.length);
  478.         std::swap(buffer_list,x.buffer_list);
  479.         std::swap(free_list,x.free_list);
  480.         std::swap(next_avail,x.next_avail);
  481.         std::swap(list_node_allocator,x.list_node_allocator);
  482.         std::swap(value_allocator,x.value_allocator);
  483.         std::swap(buffer_allocator,x.buffer_allocator);
  484.         std::swap(last,x.last);
  485. #else
  486.         ::swap(node, x.node);
  487.         ::swap(length, x.length);
  488.         ::swap(buffer_list,x.buffer_list);
  489.         ::swap(free_list,x.free_list);
  490.         ::swap(next_avail,x.next_avail);
  491.         ::swap(list_node_allocator,x.list_node_allocator);
  492.         ::swap(value_allocator,x.value_allocator);
  493.         ::swap(buffer_allocator,x.buffer_allocator);
  494.         ::swap(last,x.last);
  495. #endif
  496.     }
  497.  
  498.   protected:
  499.  
  500.     void transfer (iterator position, iterator first, iterator last)
  501.     {
  502.         (*(link_type((*last.node).prev))).next = position.node;
  503.         (*(link_type((*first.node).prev))).next = last.node;
  504.         (*(link_type((*position.node).prev))).next = first.node;
  505.         link_type tmp = link_type((*position.node).prev);
  506.         (*position.node).prev = (*last.node).prev;
  507.         (*last.node).prev = (*first.node).prev;
  508.         (*first.node).prev = tmp;
  509.     }
  510.  
  511.   public:
  512.     //
  513.     // list operations.
  514.     //
  515.     void splice (iterator position, list<T>& x)
  516.     {
  517.         if (!x.empty())
  518.         {
  519.             transfer(position, x.begin(), x.end());
  520.             length += x.length;
  521.             x.length = 0;
  522.         }
  523.     }
  524.     void splice (iterator position, list<T>& x, iterator i)
  525.     {
  526.         iterator j = i;
  527.         transfer(position, i, ++j);
  528.         ++length;
  529.         --x.length;
  530.     }
  531.     void splice (iterator position, list<T>& x, iterator first, iterator last)
  532.     {
  533.         if (first != last)
  534.         {
  535.             difference_type n;
  536.             __initialize(n, difference_type(0));
  537.             distance(first, last, n);
  538.             x.length -= n;
  539.             length += n;
  540.             transfer(position, first, last);
  541.         }
  542.     }
  543.     void remove  (const T& value);
  544.     void unique  ();
  545.     void merge   (list<T>& x);
  546.     void reverse ();
  547.     void sort    ();
  548.  
  549. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  550.     template<class Predicate>       void remove_if (Predicate pred);
  551.     template<class BinaryPredicate> void unique    (BinaryPredicate pred);
  552.     template<class Compare>         void merge     (list<T>& x, Compare comp);
  553.     template<class Compare>         void sort      (Compare comp);
  554. #endif
  555. };
  556.  
  557. template <class T>
  558. inline bool operator== (const list<T>& x, const list<T>& y)
  559. {
  560.     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  561. }
  562.  
  563. template <class T>
  564. inline bool operator< (const list<T>& x, const list<T>& y)
  565. {
  566.     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  567. }
  568.  
  569. template <class T>
  570. void list<T>::deallocate_buffers ()
  571. {
  572.     while (buffer_list)
  573.     {
  574.         buffer_pointer tmp = buffer_list;
  575.         buffer_list = (buffer_pointer)(buffer_list->next_buffer);
  576.         list_node_allocator.deallocate(tmp->buffer);
  577.         buffer_allocator.deallocate(tmp);
  578.     }
  579.     free_list = 0;
  580.     next_avail = 0;
  581.     last = 0;
  582. }
  583.  
  584. //
  585. // This requires that T have a default constructor.
  586. //
  587.  
  588. template <class T>
  589. void list<T>::resize (size_type new_size)
  590. {
  591.     T value;
  592.     if (new_size > size())
  593.         insert(end(), new_size - size(), value);
  594.     else if (new_size < size())
  595.     {
  596.         iterator tmp = begin();
  597.         advance(tmp, (difference_type) new_size);
  598.         erase(tmp, end());
  599.     }
  600. }
  601.  
  602. template <class T>
  603. void list<T>::resize (size_type new_size, T value)
  604. {
  605.     if (new_size > size())
  606.         insert(end(), new_size - size(), value);
  607.     else if (new_size < size())
  608.     {
  609.         iterator tmp = begin();
  610.         advance(tmp, (difference_type) new_size);
  611.         erase(tmp, end());
  612.     }
  613. }
  614.  
  615. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  616. template <class T>
  617. template<class InputIterator>
  618. void list<T>::insert (iterator position, InputIterator first,
  619.                       InputIterator locallast)
  620. {
  621.     while (first != locallast) insert(position, *first++);
  622. }
  623. #else
  624. template <class T>
  625. void list<T>::insert (iterator position, const_iterator first,
  626.                       const_iterator locallast)
  627. {
  628.     while (first != locallast) insert(position, *first++);
  629. }
  630. template <class T>
  631. void list<T>::insert (iterator position, const T* first, const T* locallast)
  632. {
  633.     while (first != locallast) insert(position, *first++);
  634. }
  635. #endif
  636.  
  637. template <class T>
  638. void list<T>::insert (iterator position, size_type n, const T& x)
  639. {
  640.     while (n--) insert(position, x);
  641. }
  642.  
  643. template <class T>
  644. void list<T>::erase (iterator first, iterator locallast)
  645. {
  646.     while (first != locallast) erase(first++);
  647. }
  648.  
  649. template <class T>
  650. list<T>& list<T>::operator= (const list<T>& x)
  651. {
  652.     if (this != &x)
  653.     {
  654.         iterator first1 = begin();
  655.         iterator last1 = end();
  656.         const_iterator first2 = x.begin();
  657.         const_iterator last2 = x.end();
  658.         while (first1 != last1 && first2 != last2) *first1++ = *first2++;
  659.         if (first2 == last2)
  660.             erase(first1, last1);
  661.         else
  662.             insert(last1, first2, last2);
  663.     }
  664.     return *this;
  665. }
  666.  
  667. template <class T>
  668. void list<T>::remove (const T& value)
  669. {
  670.     iterator first = begin();
  671.     iterator last = end();
  672.     while (first != last)
  673.     {
  674.         iterator next = first;
  675.         ++next;
  676.         if (*first == value) erase(first);
  677.         first = next;
  678.     }
  679. }
  680.  
  681. template <class T>
  682. void list<T>::unique ()
  683. {
  684.     iterator first = begin();
  685.     iterator last = end();
  686.     if (first == last) return;
  687.     iterator next = first;
  688.     while (++next != last)
  689.     {
  690.         if (*first == *next)
  691.             erase(next);
  692.         else
  693.             first = next;
  694.         next = first;
  695.     }
  696. }
  697.  
  698. template <class T>
  699. void list<T>::merge (list<T>& x)
  700. {
  701.     iterator first1 = begin();
  702.     iterator last1 = end();
  703.     iterator first2 = x.begin();
  704.     iterator last2 = x.end();
  705.     while (first1 != last1 && first2 != last2)
  706.     {
  707.         if (*first2 < *first1)
  708.         {
  709.             iterator next = first2;
  710.             transfer(first1, first2, ++next);
  711.             first2 = next;
  712.         }
  713.         else
  714.             first1++;
  715.     }
  716.     if (first2 != last2) transfer(last1, first2, last2);
  717.     length += x.length;
  718.     x.length = 0;
  719. }
  720.  
  721. template <class T>
  722. void list<T>::reverse ()
  723. {
  724.     if (size() < 2) return;
  725.     for (iterator first = ++begin(); first != end();)
  726.     {
  727.         iterator old = first++;
  728.         transfer(begin(), old, first);
  729.     }
  730. }
  731.  
  732. template <class T>
  733. void list<T>::sort ()
  734. {
  735.     if (size() < 2) return;
  736.     list<T> carry;
  737.     list<T> counter[64];
  738.     int fill = 0;
  739.     while (!empty())
  740.     {
  741.         carry.splice(carry.begin(), *this, begin());
  742.         int i = 0;
  743.         while (i < fill && !counter[i].empty())
  744.         {
  745.             counter[i].merge(carry);
  746.             carry.swap(counter[i++]);
  747.         }
  748.         carry.swap(counter[i]);
  749.         if (i == fill) ++fill;
  750.     }
  751.     while (fill--) merge(counter[fill]);
  752. }
  753.  
  754. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  755. template<class T>
  756. template<class Predicate> void list<T>::remove_if (Predicate pred)
  757. {
  758.     iterator first = begin();
  759.     iterator last = end();
  760.     while (first != last)
  761.     {
  762.         iterator next = first;
  763.         ++next;
  764.         if (pred(*first)) erase(first);
  765.         first = next;
  766.     }
  767. }
  768.  
  769. template<class T>
  770. template<class BinaryPredicate> void list<T>::unique (BinaryPredicate pred)
  771. {
  772.     iterator first = begin();
  773.     iterator last = end();
  774.     if (first == last) return;
  775.     iterator next = first;
  776.     while (++next != last)
  777.     {
  778.         if (pred(*first, *next))
  779.             erase(next);
  780.         else
  781.             first = next;
  782.         next = first;
  783.     }
  784. }
  785.  
  786. template<class T>
  787. template<class Compare> void list<T>::merge (list<T>& x, Compare comp)
  788. {
  789.     iterator first1 = begin();
  790.     iterator last1  = end();
  791.     iterator first2 = x.begin();
  792.     iterator last2  = x.end();
  793.     while (first1 != last1 && first2 != last2)
  794.     {
  795.         if (comp(*first2, *first1))
  796.         {
  797.             iterator next = first2;
  798.             transfer(first1, first2, ++next);
  799.             first2 = next;
  800.         }
  801.         else
  802.             first1++;
  803.     }
  804.     if (first2 != last2) transfer(last1, first2, last2);
  805.     length += x.length;
  806.     x.length = 0;
  807. }
  808.  
  809. template<class T>
  810. template<class Compare> void list<T>::sort (Compare comp)
  811. {
  812.     if (size() < 2) return;
  813.     list<T> carry;
  814.     list<T> counter[64];
  815.     int fill = 0;
  816.     while (!empty())
  817.     {
  818.         carry.splice(carry.begin(), *this, begin());
  819.         int i = 0;
  820.         while (i < fill && !counter[i].empty())
  821.         {
  822.             counter[i].merge(carry, comp);
  823.             carry.swap(counter[i++]);
  824.         }
  825.         carry.swap(counter[i]);
  826.         if (i == fill) ++fill;
  827.     }
  828.     while (fill--) merge(counter[fill]);
  829. }
  830. #endif /*RWSTD_NO_MEMBER_TEMPLATES*/
  831.  
  832. #ifndef RWSTD_NO_NAMESPACE
  833. }
  834. #endif
  835.  
  836. #undef Allocator
  837. #undef list
  838.  
  839. #endif /*__STD_LIST__*/
  840.